计蒜客 贝壳找房与送水员

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
好题
发现了两个v的做法
但是没发现一个v的
按照之前的思路死活做不出来，这时候要跳出之前的思维模式（重点！重点！重点！）
不再是按照对位的边形成的树上找了
而是考虑有没有环
题解：
1个v：现在题意变成了要求多组单向可达关系加最少有向边的问题。考虑每
个弱联通子图，如果是个dag的话最少需要v-1个魔法（构造方法：用链将拓扑序串起
来），否则的话至少需要v个魔法（一个大环）。然后加起来就好了。
发现不会找弱连通子图哇哇哇
dfs3+dfs2，再开两个vis数组
丑的不行的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008,shiwan=100000;
int n;
char s[20];
int cnt;
int a[N],b[N];
bool vis[N],ins[N];
vector<int> v;
int nume,head[N];
int nume_2,head_2[N];
struct edge{
	int to,nxt;
}e[N<<1],e_2[N<<1];
inline void add_edge(int x,int y)
{
	e[++nume]=(edge){y,head[x]};head[x]=nume;
}
inline void add_edge_2(int x,int y)
{
	e_2[++nume_2]=(edge){y,head_2[x]};head_2[x]=nume_2;
}
int ans;
inline void dfs(int x)
{
	vis[x]=0;
	for(int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to]){
			dfs(e[i].to);
		}
	}
}
bool flag;
inline void dfs2(int x)
{
	vis[x]=0;
	ins[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to]){
			dfs2(e[i].to);
		}
		else if(ins[e[i].to]){
			flag=1;
		}
	}
	ins[x]=0;
}
bool vis2[N];
inline void dfs3(int x)
{
	if(vis[x]){
		dfs2(x);
	}
	vis2[x]=1;
	for(int i=head_2[x];i;i=e_2[i].nxt){
		if(!vis2[e_2[i].to]){
			dfs3(e_2[i].to);
		}
	}
}
inline void solve()
{
	if(cnt==0){
		for(int i=1;i<=n;++i){
			if(a[i]!=b[i]){
				puts("-1");
				return;
			}
		}
		puts("0");
		return;
	}
	if(cnt==1){
		for(int i=1;i<=n;++i){
			if(a[i]!=b[i]){
				add_edge(a[i],b[i]);
				add_edge_2(a[i],b[i]);
				add_edge_2(b[i],a[i]);
				if(!vis[a[i]]){
					v.pb(a[i]);
					vis[a[i]]=1;
				}
				if(!vis[b[i]]){
					v.pb(b[i]);
					vis[b[i]]=1;
				}
			}
		}
		ans=v.size();
		for(int i=0;i<v.size();++i){
			if(vis[v[i]]){
				flag=0;
				dfs3(v[i]);
				if(!flag)	--ans;
			}
		}
		printf("%d",ans);
		return;
	}
	if(cnt==2){
		for(int i=1;i<=n;++i){
			if(a[i]!=b[i]){
				add_edge(a[i],b[i]);
				add_edge(b[i],a[i]);
				if(!vis[a[i]]){
					v.pb(a[i]);
					vis[a[i]]=1;
				}
				if(!vis[b[i]]){
					v.pb(b[i]);
					vis[b[i]]=1;
				}
			}
		}
		ans=v.size();
		for(int i=0;i<v.size();++i){
			if(vis[v[i]]){
				dfs(v[i]);
				--ans;
			}
		}
		printf("%d",ans);
		return;
	}
}
int main()
{
	//freopen("D.in","r",stdin);
	n=read();
	scanf("%s",s+1);
	if(s[1]=='V')	++cnt;
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	scanf("%s",s+1);
	if(s[1]=='V')	++cnt;
	for(int i=1;i<=n;++i){
		b[i]=read();
	}
	solve();
	return 0;
}